#include "myTree.h"
#include<algorithm>
using namespace std;
//创建树结点
TreeNode::TreeNode() {
	data = '\0';
	leftChild = NULL;    //左孩子
	rightChild = NULL;   //右孩子
}
TreeNode::TreeNode(const char st[], int& index) {
	data = st[index];
	index++;
	if (st[index] == '@') {
		leftChild = NULL;
	}
	else
		leftChild = new TreeNode(st, index);//设置左子树
	index++;
	if (st[index] == '@') {
		rightChild = NULL;

	}
	else
		rightChild = new TreeNode(st, index);//设置右子树
}
MyTree::MyTree(const char st[]) {
	int i = 0;
	if (st[0] == '@')root = NULL;
	else root = new TreeNode(st, i);
	isThread = 0;
}
TreeNode::TreeNode(char val, TreeNode* l, TreeNode* r, NodeTag lt, NodeTag rt) {
	data = val;
	lTag = lt;
	rTag = rt;
	if (l)leftChild = new TreeNode(l->data, l->leftChild, l->rightChild, l->lTag, l->rTag);
	else leftChild = NULL;
	if (r)rightChild = new TreeNode(r->data, r->leftChild, r->rightChild, r->lTag, r->rTag);
	else rightChild = NULL;
}
//无参构造
MyTree::MyTree() {
	root = NULL;
	isThread = 0;
}
//拷贝函数
MyTree::MyTree(const MyTree& T) {
	isThread = T.isThread;
	if (T.root == NULL)return;
	else root = new TreeNode(T.root->data, T.root->leftChild, T.root->rightChild, T.root->lTag, T.root->rTag);
}
//销毁树结点
TreeNode::~TreeNode() {}
//销毁树
MyTree::~MyTree() {
	if (root)delete root; root = NULL;
}
//前序遍历
void qianxv(TreeNode* tr) {
	if (tr == NULL)return;
	cout << tr->data;
	qianxv(tr->leftChild);
	qianxv(tr->rightChild);
}
void MyTree::preOrderTraverse() {
	qianxv(root);
}
//中序遍历
void zhongxv(TreeNode* tr) {
	if (tr == NULL)return;
	zhongxv(tr->leftChild);
	cout << tr->data;
	zhongxv(tr->rightChild);
}
void Zhongxv(TreeNode* p) {
	if (p == NULL) {
		return;
	}
	else {
		if (p->lTag == Link)Zhongxv(p->leftChild);
		cout << p->data;
		if (p->rTag == Link)Zhongxv(p->rightChild);
	}
}
void MyTree::inOrderTraverse() {
	if (!isThread)
		zhongxv(root);
	else Zhongxv(root);
}
//后序遍历
void houxv(TreeNode* tr) {
	if (tr == NULL)return;
	houxv(tr->leftChild);
	houxv(tr->rightChild);
	cout << tr->data;
}
void MyTree::postOrderTraverse() {
	houxv(root);
}
//线索化
bool MyTree::inOrderThreading() {
	isThread = 1;
	if (root == NULL)return false;
	else {
		TreeNode* T = new TreeNode;
		TreeNode* R = new TreeNode;
		T->lTag = Link;
		T->rTag = Thread;
		T->rightChild = T;
		T->leftChild = root;
		R = T;
		InOrderTh(root, R);
		R->rTag = Thread;
		R->rightChild = T;
		T->rightChild = R;
		return true;
	}
}
void InOrderTh(TreeNode* p, TreeNode*& R)
{
	if (p != NULL) {
		InOrderTh(p->leftChild, R);
		if (p->leftChild == NULL) {
			p->lTag = Thread;
			p->leftChild = R;
		}
		if (R->rightChild == NULL) {
			R->rTag = Thread;
			R->rightChild = p;
		}
		R = p;
		InOrderTh(p->rightChild, R);
	}
}

//计算二叉树的叶子结点数
int leaf(TreeNode* tr) {
	if (!tr)return 0;
	else if (!tr->leftChild && !tr->rightChild)return 1;
	else return leaf(tr->leftChild) + leaf(tr->rightChild);
}
int MyTree::countLeaf() {
	return leaf(root);
}
//计算二叉树的深度
int height(TreeNode* tr) {
	if (tr == NULL)return 0;
	int m = height(tr->leftChild);
	int n = height(tr->rightChild);
	return (m > n) ? m + 1 : n + 1;
}
int MyTree::countHeight() {
	if (root == NULL)return 0;
	return height(root);
}
//当前树是否是线索二叉树
bool MyTree::isThreadedTree() {
	return isThread;
}
//结点定位
void qianxv(TreeNode* tr, TreeNode& cur, const char& val) {
	if (tr == NULL)return;
	if (tr->data == val) {
		cur = *tr;
		return;
	}
	qianxv(tr->leftChild, cur, val);
	qianxv(tr->rightChild, cur, val);
}
TreeNode& MyTree::locateNode(const char& val) {
	TreeNode* cur = root;
	if (this->isThreadedTree())
		while (cur)
		{
			//找到最左的点
			while (cur->lTag == Link)
			{
				cur = cur->leftChild;
			}
			if (cur->data == val)break;
			while (cur->rTag == Thread)
			{
				cur = cur->rightChild;
				if (cur->data == val)goto skip;
			}
			cur = cur->rightChild;
		}
	else {
		qianxv(root, *cur, val);
	}
skip:
	return *cur;
}
//获取前驱结点
TreeNode& MyTree::preNode(const TreeNode& cur) {
	TreeNode* N = new TreeNode;
	if (cur.lTag == Thread)
		if (cur.leftChild != root)
			return *cur.leftChild;
		else if (cur.leftChild != root) {
			*N = cur;
			while (N->lTag == Link)
			{
				N = N->leftChild;
			}
		}
	return *N;
}
//获取后继结点
TreeNode& MyTree::nextNode(const TreeNode& cur) {
	TreeNode* N = new TreeNode;
	if (cur.rTag == Thread)
		if (cur.rightChild != root)
			return *cur.rightChild;
		else if (cur.rightChild != root) {
			*N = cur;
			while (N->rTag == Link)
			{
				N = N->rightChild;
			}
		}
	return *N;
}
//输出树结点
void TreeNode::printNode()
{
	cout << this->data;
}

HuffmanTree::HuffmanTree(const int& a, const int b[]) {
	n = a;
	const int c = 2 * a - 1;
	p = new hf[c];
	for (int i = 0; i < a; i++) {
		p[i].weight = b[i];
	}
	for (int i = a; i < 2 * a - 1; i++) {
		int min1 = 999;
		int min2 = 999;
		int p1 = 0, p2 = 0;
		for (int j = 0; j < i; j++) {
			if (p[j].parent == -1) {
				if (p[j].weight < min1) {
					p2 = p1;
					min2 = min1;
					p1 = j;
					min1 = p[j].weight;
				}
				else if (p[j].weight < min2) {
					p2 = j;
					min2 = p[j].weight;
				}
			}
		}
		p[i].left = p1;
		p[i].right = p2;
		p[i].weight = p[p1].weight + p[p2].weight;
		p[p1].parent = i;
		p[p2].parent = i;
	}
}
HuffmanTree::~HuffmanTree() {
	delete p;
}
void HuffmanTree::printHuffmanCodes() {
	t* c = new t[n];
	int* v = new int[n];
	//list<int>v;
	for (int i = 0; i < n; i++) {
		//v.push_back(p[i].weight);
		v[i] = p[i].weight;
	}
	sort(v, v + n);
	for (int i = 0; i < n; i++) {
		c[i].a = v[n - 1 - i];
		//v.pop_back();
	}
	string w;
	int i = 0;
	while (p[i].parent != -1)i++;
	w.push_back('0');
	if (p[i].left != -1)l(p[p[i].left], w, c);
	w.pop_back();
	w.push_back('1');
	if (p[i].right != -1)l(p[p[i].right], w, c);
	for (int i = 0; i < n; i++) {
		cout << c[i].a << ":" << c[i].b << endl;
	}
}
void HuffmanTree::l(hf q, string w, t c[]) {
	for (int i = 0; i < n; i++) {
		if (c[i].a == q.weight) {
			c[i].b = w;
		}
	}
	w.push_back('0');
	if (q.left != -1)l(p[q.left], w, c);
	w.pop_back();
	w.push_back('1');
	if (q.right != -1)l(p[q.right], w, c);
}